/**
 * 链表实现类 主要实现链表的各种操作
 * 
 * @author 杨满球（本地）
 *
 */
class LinkList {
	// 链表头节点
	private Node head;

	// 无参构造方法
	public LinkList() {
		head = new Node();
	}

	/**
	 * 清空整个链表
	 */
	public void clear() {
		head.setNextNode(null);
	}

	/**
	 * 判断链表是否为空
	 * 
	 * @return 链表为空返回true，否则返回false
	 */
	public boolean isEmpty() {
		return head.getNextNode() == null;
	}

	/**
	 * 获得链表节点个数
	 * 
	 * @return 链表节点个数
	 */
	public int length() {
		int length = 0;
		// 指向首节点
		Node p = this.getHead().getNextNode();
		// 循环统计节点数
		while (p != null) {
			p = p.getNextNode();
			length++;
		}
		return length;
	}

	/**
	 * 获得当前链表的头节点
	 * 
	 * @return
	 */
	public Node getHead() {
		return head;
	}

	/**
	 * 获得指定索引的节点
	 * 
	 * @param index
	 *            指定索引
	 * @return 指定索引处的节点
	 * @throws Exception
	 *             索引非法
	 */
	public Node getNode(int index) throws Exception {
		// 判断索引是否非法
		if (index < 0 || index >= this.length()) {
			throw new Exception("Index is illegal!");
		}
		int i = 0;
		Node p = head.getNextNode();
		// 循环查找节点
		while (i < index) {
			p = p.getNextNode();
			i++;
		}
		return p;
	}

	/**
	 * 获得指定索引节点的数据
	 * 
	 * @param index
	 *            指定的索引
	 * @return 指定的索引处节点的数据
	 * @throws Exception
	 *             索引非法
	 */
	public Object getNodeData(int index) throws Exception {
		Node p = this.getNode(index);
		return p.getData();
	}

	/**
	 * 根据数据查找该数据在链表中第一次出现的索引
	 * 
	 * @param data
	 *            指定数据
	 * @return 给定数据在链表中第一次出现的索引
	 */
	public int indexOf(Object data) {
		Node p = head.getNextNode();
		int index = 0;
		// 循环查找并比对数据
		while (p != null && !p.getData().equals(data)) {
			p = p.getNextNode();
			index++;
		}
		if (p != null) {// 找到了指定数据
			return index;
		}
		return -1;
	}

	/**
	 * 获得指定索引的上一节点
	 * 
	 * @param index
	 *            指定节点
	 * @return 指定索引的上一节点
	 * @throws Exception
	 *             索引非法
	 */
	public Node getLastNode(int index) throws Exception {
		if (index == 0) {// 获取0索引的上一节点，返回头节点
			return head;
		} else {
			Node p = this.getNode(index - 1);
			return p;
		}
	}

	/**
	 * 在指定索引处添加一个节点
	 * 
	 * @param data
	 *            需要添加节点存储的数据
	 * @param index
	 *            指定添加的索引
	 * @throws Exception
	 *             索引非法
	 */
	public void addNode(Object data, int index) throws Exception {
		Node nextNode;
		if (index == this.length()) {// 所要添加的位置为末尾，下一节点为空
			nextNode = null;
		} else {
			nextNode = this.getNode(index);
		}
		// 获得上一节点
		Node lastNode = this.getLastNode(index);
		Node p = new Node(data);
		if (nextNode != null) {// 具有下一节点，绑定下一节点
			p.setNextNode(nextNode);
		}
		// 绑定上一节点
		lastNode.setNextNode(p);
	}

	/**
	 * 移除指定索引处的节点
	 * 
	 * @param index
	 *            指定索引
	 * @throws Exception
	 *             索引非法
	 */
	public void removeNode(int index) throws Exception {
		// 获得当前节点
		Node p = getNode(index);
		// 获得当前节点的上一节点
		Node lastNode = this.getLastNode(index);
		// 判断是否有后续节点
		if (p.hasNext()) {// 有后续节点，把上一节点的下一节点指针指向下一节点
			lastNode.setNextNode(p.getNextNode());
		} else {// 无后续节点，把上一节点的下一节点指针清空
			lastNode.setNextNode(null);
		}
	}

	/**
	 * 在当前链表的后面绑定另一链表
	 * 
	 * @param 需要续接的链表
	 * @return 续借后的长链表
	 */
	public LinkList appendLinkList(LinkList l) {
		Node p = null;
		Node endNode = null;
		try {
			// 获得后续链表的首节点
			p = l.getNode(0);
			// 获得当前链表的最后一个节点
			endNode = this.getNode(this.length() - 1);
		} catch (Exception e) {
			e.printStackTrace();
		}
		// 把最后一个节点的下一节点指针指向后续链表的首节点
		endNode.setNextNode(p);
		return this;
	}

	/**
	 * 获得链表的字符串表示形式
	 * 
	 * @return 链表的字符串表示
	 */
	public String getString() {
		if (this.length() < 1) {
			return "This link list is Empty.";
		}
		Node p = head.getNextNode();
		String linkList = (String) p.getData();
		while (p.hasNext()) {
			p = p.getNextNode();
			// 以逗号分隔各个节点
			linkList = linkList + "," + p.getData();
		}
		return linkList;
	}

}
